package com.Q08;

/**
 * @version v1.0.0
 * 创建时间：2022/8/4 10:25
 */
public class Q08_11 {
    public int waysToChange(int n) {
        // 背包问题、动态规划
        // 定义：用前n种钱、凑到n的方案数
        int types = 5;
        int[] coins = new int[4];
        coins[0] =1;
        coins[1]=5;
        coins[2]=10;
        coins[3]=25;

        int[][] dp = new int[types][n+1];
        // base case
        for (int i = 0; i < types; i++) {
            dp[i][0] = 1;
        }
        // dp[i][k] = dp[i-1][k] // Buyong
        // dp[i][k] = dp[i-1][k-nums[i]] leijia
        for (int i = 1; i < types; i++) {
            int coin = coins[i-1];
            for (int j = 1; j < n + 1; j++) {
                if (j-coin>=0) {
                    dp[i][j] += dp[i][j - coin];
                }
                dp[i][j] +=  dp[i-1][j];
            }
        }
        return dp[types-1][n];
    }

    public int waysToChange2(int n) {
        // 背包问题、动态规划，状态压缩，循环剪枝
        // 定义：用凑到n的方案数
        int[] coins = new int[4];
        coins[0] = 1;
        coins[1] = 5;
        coins[2] = 10;
        coins[3] = 25;
        int MOD = 1000000007;
        int[] dp = new int[n + 1];
        // base case
        dp[0] = 1;
        // dp[k] = dp[k-nums[i]] leijia
        for (int coin : coins) {
            for (int j = coin; j < n + 1; j++) {
                dp[j] = (dp[j] + dp[j - coin])%MOD;
            }
        }

        return dp[n];
    }

    public static void main(String[] args) {
        int i = new Q08_11().waysToChange(10);
        System.out.println(i);
    }
}
